home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Connect-4 Algorithm / c4.c next >
Encoding:
C/C++ Source or Header  |  1994-11-09  |  32.1 KB  |  815 lines  |  [TEXT/R*ch]
  1. /****************************************************************************/
  2. /****************************************************************************/
  3. /**                                                                        **/
  4. /**                          Connect-4 Algorithm                           **/
  5. /**                                                                        **/
  6. /**                            By Keith Pomakis                            **/
  7. /**                     (kppomaki@jeeves.uwaterloo.ca)                     **/
  8. /**                                                                        **/
  9. /**                               Fall, 1993                               **/
  10. /**                                                                        **/
  11. /****************************************************************************/
  12. /**                                                                        **/
  13. /**  This file provides the functions necessary to implement a front-end-  **/
  14. /**  independent, device-independent Connect-4 game.  Multiple board sizes **/
  15. /**  are supported.  It is also possible to specify the number of pieces   **/
  16. /**  necessary to connect in a row in order to win.  Therefore one can     **/
  17. /**  play Connect-3, Connect-5, etc.  An efficient tree-searching          **/
  18. /**  algorithm (making use of alpha-beta cutoff decisions) has been        **/
  19. /**  implemented to insure that the computer plays as quickly as possible. **/
  20. /**                                                                        **/
  21. /**  The declaration of the public functions necessary to use this file    **/
  22. /**  are contained in "c4.h".                                              **/
  23. /**                                                                        **/
  24. /**  In all of the public functions, the value of player can be any        **/
  25. /**  integer, where an even integer refers to player 0 and an odd integer  **/
  26. /**  refers to player 1.                                                   **/
  27. /**                                                                        **/
  28. /****************************************************************************/
  29. /****************************************************************************/
  30.  
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33. #include <time.h>
  34. #include "c4.h"
  35.  
  36. /* The static global variables required. */
  37.  
  38. #define NUM_OF_TEMP_STATES      42
  39. static long size_x, size_y, num_to_connect;
  40. static long win_places;
  41. static Boolean ***map;
  42. static Game_state real_state;
  43. static Boolean game_in_progress = FALSE, seed_chosen = FALSE;
  44. static void (*poll_function)(void) = NULL;
  45. static long poll_level;
  46. static Game_state temp_states[NUM_OF_TEMP_STATES];
  47. static Boolean temp_array[NUM_OF_TEMP_STATES];
  48. static long temp_states_allocated = 0;
  49.  
  50. /* Some macros for convenience. */
  51.  
  52. #define other(x) (((x)==1)? 0 : 1)
  53. #define real_player(x) (x & 1)
  54.  
  55. /* A declaration of the local functions. */
  56.  
  57. static void insure_game(void);
  58. static long num_of_win_places(long x, long y, long n);
  59. static void update_score(Game_state *state, long player, long x, long y);
  60. static Boolean drop_piece(Game_state *state, long player, long column);
  61. static long player_score(Game_state *state, long player);
  62. static Boolean winner(Game_state *state, long player);
  63. static Boolean tie(Game_state *state);
  64. static long goodness_of(Game_state *state, long player);
  65. static Game_state *copy_state(Game_state *state);
  66. static void destroy_state(Game_state *state);
  67. static long worst_goodness(Game_state *state, long player, long level,
  68.                                                     long depth, long so_far);
  69. static void *emalloc(unsigned int n);
  70.  
  71.  
  72. /****************************************************************************/
  73. /**                                                                        **/
  74. /**  This function specifies that the computer should call the specified   **/
  75. /**  function from time to time, in essence polling it to see if the       **/
  76. /**  front-end interface requires any attention.  The specified function   **/
  77. /**  should accept void and return void.  level is the level of lookahead  **/
  78. /**  at which the function should be called.  This level is measured from  **/
  79. /**  the bottom.  Eg. If the lookahead level is set to 6 and level is set  **/
  80. /**  to 4, with a 7x6 board, this function will be called a maximum of     **/
  81. /**  7^2 = 49 times (once for each (6-4)th = 2nd level node visited.       **/
  82. /**                                                                        **/
  83. /**  Note that if a node is not visited due to apha-beta cutoff, this      **/
  84. /**  function will not be called at that node.  Therefore only a maximum   **/
  85. /**  number of calls can be predicted (with a minimum of 1).               **/
  86. /**                                                                        **/
  87. /**  If no polling is required, the polling function can be specified as   **/
  88. /**  NULL.  This is the default.  This function can be called an arbitrary **/
  89. /**  number of times throughout any game.                                  **/
  90. /**                                                                        **/
  91. /****************************************************************************/
  92.  
  93. void
  94. poll(void (*poll_func)(void), long level)
  95. {
  96.     poll_function = poll_func;
  97.     poll_level = level;
  98. }
  99.  
  100.  
  101. /****************************************************************************/
  102. /**                                                                        **/
  103. /**  This function sets up a new game.  This must be called exactly once   **/
  104. /**  before each game is started.  Before it can be called a second time,  **/
  105. /**  end_game() must be called to destroy the previous game.               **/
  106. /**                                                                        **/
  107. /**  width and height are the desired dimensions of the game board, while  **/
  108. /**  num is the number of pieces required to connect in a row in order to  **/
  109. /**  win the game.                                                         **/
  110. /**                                                                        **/
  111. /****************************************************************************/
  112.  
  113. void
  114. new_game(long width, long height, long num)
  115. {
  116.     long i, j, k, count;
  117.  
  118.     if (game_in_progress) {
  119.         fprintf(stderr, "new_game: game already in progress\n");
  120.         exit(EXIT_FAILURE);
  121.     }
  122.  
  123.     if (width < 1 || height < 1 || num < 1) {
  124.         fprintf(stderr, "new_game: invalid parameters\n");
  125.         exit(EXIT_FAILURE);
  126.     }
  127.  
  128.     size_x = width;
  129.     size_y = height;
  130.     num_to_connect = num;
  131.     win_places = num_of_win_places(size_x, size_y, num_to_connect);
  132.  
  133.     /* Set up a random seed for making random decisions when there is */
  134.     /* equal goodness between two moves.                              */
  135.     if (!seed_chosen) {
  136.         srand(time((time_t *)0));
  137.         seed_chosen = TRUE;
  138.     }
  139.  
  140.     /* Set up the board */
  141.  
  142.     real_state.board = (char **) emalloc(size_x * sizeof(char *));
  143.     for (i=0; i<size_x; i++) {
  144.         real_state.board[i] = (char *) emalloc(size_y * sizeof(char));
  145.         for (j=0; j<size_y; j++)
  146.             real_state.board[i][j] = EMPTY;
  147.     }
  148.  
  149.     /* Set up the score array */
  150.  
  151.     real_state.score_array[0] = (long *) emalloc(win_places * sizeof(long));
  152.     real_state.score_array[1] = (long *) emalloc(win_places * sizeof(long));
  153.     for (i=0; i<win_places; i++) {
  154.         real_state.score_array[0][i] = 1;
  155.         real_state.score_array[1][i] = 1;
  156.     }
  157.  
  158.     /* Set up the map */
  159.  
  160.     map = (Boolean ***) emalloc(size_x * sizeof(Boolean **));
  161.     for (i=0; i<size_x; i++) {
  162.         map[i] = (Boolean **) emalloc(size_y * sizeof(Boolean *));
  163.         for (j=0; j<size_y; j++) {
  164.             map[i][j] = (Boolean *) emalloc(win_places * sizeof(Boolean));
  165.             for (k=0; k<win_places; k++)
  166.                 map[i][j][k] = FALSE;
  167.         }
  168.     }
  169.  
  170.     count = 0;
  171.  
  172.     /* Fill in the horizontal win positions */
  173.     for (i=0; i<size_y; i++)
  174.         for (j=0; j<size_x-num_to_connect+1; j++) {
  175.             for (k=0; k<num_to_connect; k++)
  176.                 map[j+k][i][count] = TRUE;
  177.             count++;
  178.         }
  179.  
  180.     /* Fill in the vertical win positions */
  181.     for (i=0; i<size_x; i++)
  182.         for (j=0; j<size_y-num_to_connect+1; j++) {
  183.             for (k=0; k<num_to_connect; k++)
  184.                 map[i][j+k][count] = TRUE;
  185.             count++;
  186.         }
  187.  
  188.     /* Fill in the forward diagonal win positions */
  189.     for (i=0; i<size_y-num_to_connect+1; i++)
  190.         for (j=0; j<size_x-num_to_connect+1; j++) {
  191.             for (k=0; k<num_to_connect; k++)
  192.                 map[j+k][i+k][count] = TRUE;
  193.             count++;
  194.         }
  195.  
  196.     /* Fill in the backward diagonal win positions */
  197.     for (i=0; i<size_y-num_to_connect+1; i++)
  198.         for (j=size_x-1; j>=num_to_connect-1; j--) {
  199.         /*
  200.         for (j=size_x-1; j>=size_x-num_to_connect; j--) {
  201.         */
  202.             for (k=0; k<num_to_connect; k++)
  203.                 map[j-k][i+k][count] = TRUE;
  204.             count++;
  205.         }
  206.  
  207.     real_state.num_of_pieces = 0;
  208.  
  209.     for (i=0; i<NUM_OF_TEMP_STATES; i++)
  210.         temp_array[i] = FALSE;
  211.  
  212.     game_in_progress = TRUE;
  213. }
  214.  
  215.  
  216. /****************************************************************************/
  217. /**                                                                        **/
  218. /**  This function drops a piece of the specified player into the          **/
  219. /**  specified column.  Note that column numbering starts at 0.  A value   **/
  220. /**  of TRUE is returned if the drop was successful, or FALSE otherwise.   **/
  221. /**  A drop is unsuccessful if the specified column number is invalid or   **/
  222. /**  full.                                                                 **/
  223. /**                                                                        **/
  224. /****************************************************************************/
  225.  
  226. Boolean
  227. make_move(long player, long column)
  228. {
  229.     insure_game();
  230.     if (column >= size_x || column < 0) return FALSE;
  231.     return drop_piece(&real_state, real_player(player), column);
  232. }
  233.  
  234.  
  235. /****************************************************************************/
  236. /**                                                                        **/
  237. /**  This function instructs the computer to make a move for the specified **/
  238. /**  player.  level specifies the number of levels deep the computer       **/
  239. /**  should search the game tree in order to make its decision.  This      **/
  240. /**  corresponds to the number of "moves" in the game, where each player's **/
  241. /**  turn is considered a move.  The column number of the column in which  **/
  242. /**  the piece was dropped is returned.  Note that column numbering starts **/
  243. /**  at 0.  If no move is possible (i.e. the game board is full), -1 is    **/
  244. /**  returned.  Note that for a standard 7x6 game of Connect-4, the        **/
  245. /**  computer is brain-dead at levels of three or less, while at levels of **/
  246. /**  4 or more the computer provides a challenge.                          **/
  247. /**                                                                        **/
  248. /****************************************************************************/
  249.  
  250. long
  251. automatic_move(long player, long level)
  252. {
  253.     long i, best_column, goodness, best_worst;
  254.     Game_state *temp_state;
  255.     long num_of_equal, real;
  256.  
  257.     insure_game();
  258.     real = real_player(player);
  259.  
  260.     if (level < 1) {
  261.         fprintf(stderr, "automatic_move: invalid level\n");
  262.         exit(EXIT_FAILURE);
  263.     }
  264.  
  265.     best_worst = -2000000;
  266.     best_column = -1;
  267.  
  268.     /* Simulate a drop in each of the columns and see what the results are. */
  269.  
  270.     for (i=0; i<size_x; i++) {
  271.         temp_state = copy_state(&real_state);
  272.  
  273.         /* If this column is full, ignore it as a possibility. */
  274.         if (!drop_piece(temp_state, real, i)) {
  275.             destroy_state(temp_state);
  276.             continue;
  277.         }
  278.  
  279.         /* If this drop wins the game, it is a really good move! */
  280.         if (winner(temp_state, real)) {
  281.             best_worst = 1000000;
  282.             best_column = i;
  283.         }
  284.  
  285.         /* Otherwise, look ahead to see how good this move may turn out */
  286.         /* to be (assuming the opponent makes the best moves possible). */
  287.         else
  288.             goodness = worst_goodness(temp_state, real, level, 1, best_worst);
  289.  
  290.         /* If this move looks better than the ones previously considered, */
  291.         /* remember it.                                                   */
  292.         if (goodness > best_worst) {
  293.             best_worst = goodness;
  294.             best_column = i;
  295.             num_of_equal = 1;
  296.         }
  297.  
  298.         /* If two moves are equally as good, make a random decision. */
  299.         if (goodness == best_worst) {
  300.             num_of_equal++;
  301.             if (rand()%100000 < ((float)1/(float)num_of_equal) * 100000)
  302.                 best_column = i;
  303.         }
  304.  
  305.         destroy_state(temp_state);
  306.     }
  307.  
  308.     /* Drop the piece in the column decided upon. */
  309.  
  310.     if (best_column >= 0)
  311.         drop_piece(&real_state, real, best_column);
  312.  
  313.     return best_column;
  314. }
  315.  
  316.  
  317. /****************************************************************************/
  318. /**                                                                        **/
  319. /**  This function returns the state of the current game.  The Game_state  **/
  320. /**  structure returned is defined in "c4.h".                              **/
  321. /**                                                                        **/
  322. /****************************************************************************/
  323.  
  324. Game_state
  325. get_game_state(void)
  326. {
  327.     insure_game();
  328.     return real_state;
  329. }
  330.  
  331.  
  332. /****************************************************************************/
  333. /**                                                                        **/
  334. /**  This function returns the "score" of the specified player.  This      **/
  335. /**  score is a function of how many winning positions are still available **/
  336. /**  to the player and how close he/she is to achieving each of these      **/
  337. /**  positions.  The scores of both players can be compared to observe how **/
  338. /**  well they are doing relative to each other.                           **/
  339. /**                                                                        **/
  340. /****************************************************************************/
  341.  
  342. long
  343. score_of_player(long player)
  344. {
  345.     insure_game();
  346.     return player_score(&real_state, real_player(player));
  347. }
  348.  
  349.  
  350. /****************************************************************************/
  351. /**                                                                        **/
  352. /**  This function returns TRUE if the specified player has won the game,  **/
  353. /**  and FALSE otherwise.                                                  **/
  354. /**                                                                        **/
  355. /****************************************************************************/
  356.  
  357. Boolean
  358. is_winner(long player)
  359. {
  360.     insure_game();
  361.     return winner(&real_state, player);
  362. }
  363.  
  364.  
  365. /****************************************************************************/
  366. /**                                                                        **/
  367. /**  This function returns TRUE if the board is completely full, FALSE     **/
  368. /**  otherwise.                                                            **/
  369. /**                                                                        **/
  370. /****************************************************************************/
  371.  
  372. Boolean
  373. is_tie()
  374. {
  375.     insure_game();
  376.     return tie(&real_state);
  377. }
  378.  
  379.  
  380. /****************************************************************************/
  381. /**                                                                        **/
  382. /**  This function returns the coordinates of the winning connections of   **/
  383. /**  the specified player.  It is assumed that the specified player has    **/
  384. /**  indeed won the game.  The coordinates are returned in x1, y1, x2, y2, **/
  385. /**  where (x1, y1) specifies the lower-left piece of the winning          **/
  386. /**  connection, and (x2, y2) specifies the upper-right piece of the       **/
  387. /**  winning connection.  If more than one winning connection exists, only **/
  388. /**  one will be returned.                                                 **/
  389. /**                                                                        **/
  390. /****************************************************************************/
  391.  
  392. void
  393. win_coords(long player, long *x1, long *y1, long *x2, long *y2)
  394. {
  395.     long i, j, win_pos = -1, look_for = 1 << num_to_connect;
  396.     long realplayer;
  397.     Boolean found;
  398.  
  399.     insure_game();
  400.     realplayer = real_player(player);
  401.     for (i=0; i<win_places; i++)
  402.         if (real_state.score_array[realplayer][i] == look_for)
  403.             win_pos = i;
  404.  
  405.     if (win_pos == -1) {
  406.         fprintf(stderr, "win_coords: no winner\n");
  407.         exit(EXIT_FAILURE);
  408.     }
  409.  
  410.     /* Find the lower-left piece of the winning connection. */
  411.  
  412.     found = FALSE;
  413.     for (j=0; j<size_y; j++)
  414.         for (i=0; i<size_x; i++)
  415.             if (map[i][j][win_pos] && !found) {
  416.                 *x1 = i;
  417.                 *y1 = j;
  418.                 found = TRUE;
  419.             }
  420.  
  421.     /* Find the upper-right piece of the winning connection. */
  422.  
  423.     found = FALSE;
  424.     for (j=size_y-1; j>=0; j--)
  425.         for (i=size_x-1; i>=0; i--)
  426.             if (map[i][j][win_pos] && !found) {
  427.                 *x2 = i;
  428.                 *y2 = j;
  429.                 found = TRUE;
  430.             }
  431. }
  432.  
  433.  
  434. /****************************************************************************/
  435. /**                                                                        **/
  436. /**  This function ends the current game.  It is assumed that a game is    **/
  437. /**  indeed in progress.  It is illegal to call any other game function    **/
  438. /**  immediately after this one except for new_game() and poll().          **/
  439. /**                                                                        **/
  440. /****************************************************************************/
  441.  
  442. void
  443. end_game(void)
  444. {
  445.     long i, j;
  446.  
  447.     insure_game();
  448.  
  449.     /* Free up the memory used by the game state. */
  450.  
  451.     for (i=0; i<size_x; i++) free(real_state.board[i]);
  452.     free(real_state.board);
  453.     free(real_state.score_array[0]);
  454.     free(real_state.score_array[1]);
  455.  
  456.     /* Free up the memory used by the map. */
  457.  
  458.     for (i=0; i<size_x; i++) {
  459.         for (j=0; j<size_y; j++)
  460.             free(map[i][j]);
  461.         free(map[i]);
  462.     }
  463.     free(map);
  464.  
  465.     /* Free up the memory of all the temporary states used. */
  466.  
  467.     for (i=0; i<temp_states_allocated; i++) {
  468.         temp_array[i] = FALSE;
  469.         for (j=0; j<size_x; j++) free(temp_states[i].board[j]);
  470.         free(temp_states[i].board);
  471.         free(temp_states[i].score_array[0]);
  472.         free(temp_states[i].score_array[1]);
  473.     }
  474.     temp_states_allocated = 0;
  475.  
  476.     game_in_progress = FALSE;
  477. }
  478.  
  479.  
  480. /****************************************************************************/
  481. /****************************************************************************/
  482. /**                                                                        **/
  483. /**  The following functions are local to this file and should not be      **/
  484. /**  called externally.                                                    **/
  485. /**                                                                        **/
  486. /****************************************************************************/
  487. /****************************************************************************/
  488.  
  489.  
  490. /****************************************************************************/
  491. /**                                                                        **/
  492. /**  This function insures that a game is in progress, and exits with an   **/
  493. /**  error if one is not.                                                  **/
  494. /**                                                                        **/
  495. /****************************************************************************/
  496.  
  497. static void
  498. insure_game(void)
  499. {
  500.     if (!game_in_progress) {
  501.         fprintf(stderr, "error: no game in progress\n");
  502.         exit(EXIT_FAILURE);
  503.     }
  504. }
  505.  
  506.  
  507. /****************************************************************************/
  508. /**                                                                        **/
  509. /**  This function returns the number of possible win positions on a board **/
  510. /**  of dimensions x by y with n being the number of pieces required in a  **/
  511. /**  row in order to win.                                                  **/
  512. /**                                                                        **/
  513. /****************************************************************************/
  514.  
  515. static long
  516. num_of_win_places(long x, long y, long n)
  517. {
  518.     return 4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2;
  519. }
  520.  
  521.  
  522. /****************************************************************************/
  523. /**                                                                        **/
  524. /**  This function updates the score of the specified player given that    **/
  525. /**  the player has just placed a game piece in column x, row y.           **/
  526. /**                                                                        **/
  527. /**  The specified game state is used, which may be a temporary state.     **/
  528. /**                                                                        **/
  529. /****************************************************************************/
  530.  
  531. static void
  532. update_score(Game_state *state, long player, long x, long y)
  533. {
  534.     long i;
  535.  
  536.     for (i=0; i<win_places; i++)
  537.         if (map[x][y][i]) {
  538.             state->score_array[player][i] <<= 1;
  539.             state->score_array[other(player)][i] = 0;
  540.         }
  541. }
  542.  
  543.  
  544. /****************************************************************************/
  545. /**                                                                        **/
  546. /**  This function drops a piece of the specified player into the          **/
  547. /**  specified column.  A value of TRUE is returned if the drop was        **/
  548. /**  successful, and FALSE if it was not (i.e. the specified column is     **/
  549. /**  full).                                                                **/
  550. /**                                                                        **/
  551. /**  The specified game state is used, which may be a temporary state.     **/
  552. /**                                                                        **/
  553. /****************************************************************************/
  554.  
  555. static Boolean
  556. drop_piece(Game_state *state, long player, long column)
  557. {
  558.     long y = 0;
  559.  
  560.     while (state->board[column][y] != EMPTY && ++y < size_y)
  561.         ;
  562.  
  563.     if (y == size_y) return FALSE;
  564.  
  565.     state->board[column][y] = player;
  566.     state->num_of_pieces++;
  567.     update_score(state, player, column, y);
  568.  
  569.     return TRUE;
  570. }
  571.  
  572.  
  573. /****************************************************************************/
  574. /**                                                                        **/
  575. /**  This function returns the "score" of the specified player.  This      **/
  576. /**  score is a function of how many winning positions are still available **/
  577. /**  to the player and how close he/she is to achieving each of these      **/
  578. /**  positions.  The scores of both players can be compared to observe how **/
  579. /**  well they are doing relative to each other.                           **/
  580. /**                                                                        **/
  581. /**  The specified game state is used, which may be a temporary state.     **/
  582. /**                                                                        **/
  583. /****************************************************************************/
  584.  
  585. static long
  586. player_score(Game_state *state, long player)
  587. {
  588.     long i, score = 0;
  589.  
  590.     for (i=0; i<win_places; i++)
  591.         score += state->score_array[player][i];
  592.  
  593.     return score;
  594. }
  595.  
  596.  
  597. /****************************************************************************/
  598. /**                                                                        **/
  599. /**  This function returns TRUE if the specified player has won the game,  **/
  600. /**  and FALSE otherwise.                                                  **/
  601. /**                                                                        **/
  602. /**  The specified game state is used, which may be a temporary state.     **/
  603. /**                                                                        **/
  604. /****************************************************************************/
  605.  
  606. static Boolean
  607. winner(Game_state *state, long player)
  608. {
  609.     long i, look_for = 1 << num_to_connect;
  610.  
  611.     for (i=0; i<win_places; i++)
  612.         if (state->score_array[player][i] == look_for)
  613.             return TRUE;
  614.  
  615.     return FALSE;
  616. }
  617.  
  618.  
  619. /****************************************************************************/
  620. /**                                                                        **/
  621. /**  This function returns TRUE if the board is completely full, FALSE     **/
  622. /**  otherwise.                                                            **/
  623. /**                                                                        **/
  624. /**  The specified game state is used, which may be a temporary state.     **/
  625. /**                                                                        **/
  626. /****************************************************************************/
  627.  
  628. static Boolean
  629. tie(Game_state *state)
  630. {
  631.     return (state->num_of_pieces == size_x * size_y);
  632. }
  633.  
  634.  
  635. /****************************************************************************/
  636. /**                                                                        **/
  637. /**  This function returns a measure of the "goodness" of the specified    **/
  638. /**  state for the specified player.  This goodness value is calculated by **/
  639. /**  subtracting the score of the player's opponent from the player's own  **/
  640. /**  score.  A positive value will result if the specified player is in a  **/
  641. /**  better situation than his/her opponent.                               **/
  642. /**                                                                        **/
  643. /****************************************************************************/
  644.  
  645. static long
  646. goodness_of(Game_state *state, long player)
  647. {
  648.     return player_score(state, player) - player_score(state, other(player));
  649. }
  650.  
  651.  
  652. /****************************************************************************/
  653. /**                                                                        **/
  654. /**  This function will return a copy of the specified state.  For         **/
  655. /**  efficiency, an array of allocated temporary states is kept, so that   **/
  656. /**  memory does not have to be allocated for a new state every time this  **/
  657. /**  function is called.  When the copy is finished with, it must be       **/
  658. /**  destroyed with destroy_state().                                       **/
  659. /**                                                                        **/
  660. /****************************************************************************/
  661.  
  662. static Game_state *
  663. copy_state(Game_state *state)
  664. {
  665.     long i, j, k;
  666.  
  667.     for (i=0; i<temp_states_allocated; i++)
  668.         if(!temp_array[i]) break;
  669.  
  670.     if (i==temp_states_allocated) {
  671.         if (i==NUM_OF_TEMP_STATES) {
  672.             fprintf(stderr, "copy_state: too many temp states\n");
  673.             exit(EXIT_FAILURE);
  674.         }
  675.  
  676.         /* Allocate space for the board */
  677.  
  678.         temp_states[i].board = (char **) emalloc(size_x * sizeof(char *));
  679.         for (j=0; j<size_x; j++)
  680.             temp_states[i].board[j] = (char *) emalloc(size_y * sizeof(char));
  681.  
  682.         /* Allocate space for the score array */
  683.  
  684.         temp_states[i].score_array[0] =
  685.                                 (long *) emalloc(win_places * sizeof(long));
  686.         temp_states[i].score_array[1] =
  687.                                 (long *) emalloc(win_places * sizeof(long));
  688.  
  689.         temp_states_allocated++;
  690.     }
  691.  
  692.     temp_array[i] = TRUE;
  693.  
  694.     /* Copy the board */
  695.  
  696.     for (j=0; j<size_x; j++)
  697.         for (k=0; k<size_y; k++)
  698.             temp_states[i].board[j][k] = state->board[j][k];
  699.  
  700.     /* Copy the score array */
  701.  
  702.     for (j=0; j<win_places; j++) {
  703.         temp_states[i].score_array[0][j] = state->score_array[0][j];
  704.         temp_states[i].score_array[1][j] = state->score_array[1][j];
  705.     }
  706.  
  707.     return &temp_states[i];
  708. }
  709.  
  710.  
  711. /****************************************************************************/
  712. /**                                                                        **/
  713. /**  This function destroys the specified game state (assumed to have been **/
  714. /**  created by copy_state()).  For efficiency, the memory used by the     **/
  715. /**  state is not deallocated, so that copy_state() may use this memory    **/
  716. /**  again for a new state.                                                **/
  717. /**                                                                        **/
  718. /****************************************************************************/
  719.  
  720. static void
  721. destroy_state(Game_state *state)
  722. {
  723.     long i, j;
  724.  
  725.     for (i=0; i<temp_states_allocated; i++)
  726.         if(state == &temp_states[i]) break;
  727.  
  728.     if (i==temp_states_allocated) {
  729.         fprintf(stderr, "destroy_state: state doesn't exist\n");
  730.         exit(EXIT_FAILURE);
  731.     }
  732.  
  733.     temp_array[i] = FALSE;
  734. }
  735.  
  736.  
  737. /****************************************************************************/
  738. /**                                                                        **/
  739. /**  This function determines how good the specified state may turn out to **/
  740. /**  be for the specified player.  It does this by looking ahead level     **/
  741. /**  moves.  It is assumed that both the specified player and the opponent **/
  742. /**  may make the best move possible.  Since this function is recursive,   **/
  743. /**  depth keeps track of the current depth of recursion.  so_far keeps    **/
  744. /**  track of the best worst goodness (if you dig my meaning) so far, so   **/
  745. /**  that if a goodness worse than that crops up, the game tree can be     **/
  746. /**  pruned to avoid searching unneccessary paths (this technique is       **/
  747. /**  called alpha-beta cutoff).                                            **/
  748. /**                                                                        **/
  749. /**  The specified poll function (if any) is called at the appropriate     **/
  750. /**  level.                                                                **/
  751. /**                                                                        **/
  752. /**  The worst goodness that the specified state can produce in the number **/
  753. /**  of moves (levels) searched is returned.  This is the best the         **/
  754. /**  specified player can hope to achieve with this state (since it is     **/
  755. /**  assumed that the opponent will make the best moves possible).         **/
  756. /**                                                                        **/
  757. /****************************************************************************/
  758.  
  759. static long
  760. worst_goodness(Game_state *state, long player, long level, long depth,
  761.                            long so_far)
  762. {
  763.     long i, goodness, best;
  764.     Game_state *temp_state;
  765.  
  766.     if (poll_function && level-depth==poll_level) (*poll_function)();
  767.     if (level == depth)
  768.         return goodness_of(state, player);
  769.     else {
  770.         /* Assume it is the other player's turn. */
  771.         best = -2000000;
  772.         for(i=0; i<size_x; i++) {
  773.             temp_state = copy_state(state);
  774.             if (!drop_piece(temp_state, other(player), i)) {
  775.                 destroy_state(temp_state);
  776.                 continue;
  777.             }
  778.             if (winner(temp_state, other(player)))
  779.                 goodness = 1000000 - depth;
  780.             else
  781.                 goodness = worst_goodness(temp_state, other(player), level,
  782.                                                 depth+1, best);
  783.             if (goodness > best)
  784.                 best = goodness;
  785.             destroy_state(temp_state);
  786.             if (-best < so_far) break;
  787.         }
  788.  
  789.         /* What's good for the other player is bad for this one. */
  790.         return -best;
  791.     }
  792. }
  793.  
  794.  
  795. /****************************************************************************/
  796. /**                                                                        **/
  797. /**  A safer version of malloc().                                          **/
  798. /**                                                                        **/
  799. /****************************************************************************/
  800.  
  801. void *
  802. emalloc(unsigned int n)
  803. {
  804.     void *ptr;
  805.  
  806.     ptr = (void *) malloc(n);
  807.     if ( ptr == NULL ) {
  808.         fprintf(stderr,"c4: emalloc() - Can't allocate %d bytes.\n", n);
  809.         exit(EXIT_FAILURE);
  810.     }
  811.     return ptr;
  812. }
  813.  
  814.  
  815.